Auto-completion of user queries improves the efficiency and ease by which users interact with a database or a search service. Word-level auto-completion allows a user to type the first few characters of an intended input word, and select the intended input word from a list of most likely completions of the inputted characters. Phrase-level auto-completion allows a user to provide the first few characters or the first one or more words of an intended input phrase, and select the intended input phrase from a list of most likely completions of the inputted characters or word(s).
Many techniques, statistical or otherwise, have been employed to improve the accuracy (e.g., as measured by user selection) of the list of auto-completions provided to the user. However, different state of the art techniques are biased toward different aspects of predictive information, and are not conducive to being combined with other techniques. As a result, it is challenging to provide an integrated method that effectively combines multiple aspects of predictive information to generate suitable completion candidates for the user.